package 回溯;

import java.util.ArrayList;
import java.util.List;

/**
 * @author TTDB
 * @create 2025/9/18
 */
public class partition {
     public List<List<String>> partition(String s){
        List<List<String>> res = new ArrayList<>();
        dfs(res, new ArrayList<>(), s, 0);
        return res;
     }
     public void dfs(List<List<String>> res, List<String> path, String s, int start){
        if(start == s.length()){
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i = start; i < s.length(); i++){
            if(isPalindrome(s, start, i)){
                path.add(s.substring(start, i + 1));
                dfs(res, path, s, i + 1);
                path.remove(path.size() - 1);
            }
        }
     }

    private boolean isPalindrome(String s, int start, int i) {
         while(start < i){
             if(s.charAt(start) != s.charAt(i)){
                 return false;
             }
             start++;
             i--;
         }
         return true;
    }
}
